package number_operatation.leetcode.easy;

/**
 * @author bruin_du
 * @description 0～n-1中缺失的数字
 * @date 2022/5/17 19:13
 **/
public class Offer53II_MissingNumber {
    public int missingNumber(int[] nums){

        //方法一：位运算
        // int num = 0;
        // for(int i = 0 ; i < nums.length ; i++){
        //     num ^= nums[i];
        //     num ^= i + 1;
        // }
        // return num;

        //方法二：二分查找
        int i = 0,j = nums.length - 1;
        //因为i和j肯定要先相等,相等后还会进入循环
        //i和j还会进行最后的变化
        while(i <= j){
            int mid = (j - i >> 1) + i;
            if(nums[mid] == mid)
                i = mid + 1;
            else
                j = mid - 1;
        }
        //跳出时，变量 i 和 j 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回 i 即可
        return i;
    }
}
